package own.stu.jobgib.playown.alg.leetcode.editor.cn;

//你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。 
//
// 给定一个数字 n，找出可形成完整阶梯行的总行数。 
//
// n 是一个非负整数，并且在32位有符号整型的范围内。 
//
// 示例 1: 
//
// 
//n = 5
//
//硬币可排列成以下几行:
//¤
//¤ ¤
//¤ ¤
//
//因为第三行不完整，所以返回2.
// 
//
// 示例 2: 
//
// 
//n = 8
//
//硬币可排列成以下几行:
//¤
//¤ ¤
//¤ ¤ ¤
//¤ ¤
//
//因为第四行不完整，所以返回3.
// 
// Related Topics 数学 二分查找 
// 👍 95 👎 0



public class ArrangingCoins{
    public static void main(String[] args) {
        Solution solution = new ArrangingCoins().new Solution();
        System.out.println(solution.arrangeCoins(1));
        System.out.println(solution.arrangeCoins(2));
        System.out.println(solution.arrangeCoins(3));
        System.out.println(solution.arrangeCoins(4));
        System.out.println(solution.arrangeCoins(5));
        System.out.println(solution.arrangeCoins(6));
        System.out.println(solution.arrangeCoins(7));
        System.out.println(solution.arrangeCoins(8));
        System.out.println(solution.arrangeCoins(9));
        System.out.println(solution.arrangeCoins(10));
        System.out.println(solution.arrangeCoins(11));
        System.out.println(solution.arrangeCoins(1804289383));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int arrangeCoins(int n) {
            if(n <= 1){
                return n;
            }

            int l = 1, r = (int)Math.sqrt(2L * n);
            int m = -1;
            while(l + 1 < r){
                m = (r - l) / 2 + l;
                if(check(n, m)){
                    l = m;
                }else{
                    r = m;
                }
            }

            if(check(n, r)) return r;
            else return l;
        }

        private boolean check(int n, int row){
            return 1L * row * (row + 1) >> 1 <= n;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
